/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.array;

import java.util.Arrays;

/**
 * <p>
 * 给定一个数组求得下一个字典排序的序列 
 * 1,2,3 → 1,3,2 
 * 3,2,1 → 1,2,3 
 * 1,1,5 → 1,5,1
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com 2015年5月24日
 */
public class NextPermutation {

    public void nextPermutation(int[] nums) {
        int n = nums.length;
         //记录最后一个从下降序列到上升序列的转折点
         int pivot = -1;
         for(int i= n-1;i>0;i--){
             if(nums[i]>nums[i-1]){
                 pivot = i-1;//记录的是前一个位置
                 break;
             }
         }
         //存在
         if(pivot>=0){
             for(int i=n-1;i>pivot;i--){
                 
                 if(nums[i]>nums[pivot]){
                     //交换和pivot最接近又大于它的数字
                     int tmp = nums[pivot];
                     nums[pivot] = nums[i];
                     nums[i] = tmp;
                     //升序排列，尽可能小
                     Arrays.sort(nums,pivot+1, n);
                     return;
                 }
             }
         }else{
             //如果是倒序，那么下一个排列是升序
             Arrays.sort(nums);
         }
     }
}
